package leetcode;

import java.util.Arrays;

public class LC21 {
    /*

    编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
    每行的元素从左到右升序排列。
    每列的元素从上到下升序排列。


    另一种解法：
    感觉我的方法也不错，官方的是一行或一列的切割，我的是一个一个矩阵的切割，可以看看。
     找到一个切割点，将矩阵切割为四部分，该点必须是第一个>=target的点，那么该点左上部分矩阵和右下部分的矩阵中肯定无解，所以只需递归右上部分和左下部分的矩阵
     根据对角线查询，对角线的值一定是当前行、当前列最大的值，
     那么当次对角线值小于目标值时，以当前行、当前列为界限，可分隔为四块，
     其中左上的最大值（当前行 - 1 ，当前列 - 1）比目标值小，可不考虑
     而右下的最小值比目标值大，也不考虑
     只需对左下和右上两块再做递归
     */
    public static void main(String[] args) {
        LC21 lc21 = new LC21();
        System.out.println(lc21.searchMatrix(new int[][]{{-1, 3}}, 3));
        System.out.println(lc21.searchMatrix(new int[][]{{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}}, 15));
        System.out.println(lc21.searchMatrix(new int[][]{{1, 3, 5, 7, 9}, {2, 4, 6, 8, 10}, {11, 13, 15, 17, 19}, {12, 14, 16, 18, 20}, {21, 22, 23, 24, 25}}, 13));
        System.out.println(lc21.searchMatrix(new int[][]{{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {18, 21, 23, 26, 30}}, 5));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            } else {
                ++x;
            }
        }
        return false;
    }
}
